\subsection{Running Time Analysis}\label{sec:time}

% We have to do this part before we analyze the approximation ratio since we need this to guarantee that the graphs are not far apart in terms of density.  The goal of this section is to show that if we run the algorithm from scratch then we will finish in time $O(D\log n)$.
In this section we analyze the time that it takes for the nodes to generate an approximation to the densest subgraph. Algorithm~\ref{algo:maintain} continuously runs this procedure so that it always maintains an approximation that is guaranteed to be near-optimal since we assume that the network does not change too quickly. 
%(See Section~\ref{sec:approx} for details.) 
The time that it takes for Algorithm~\ref{algo:maintain} to compute a complete family of subgraphs is simply $O(Dp) = O(D\log_{1+\epsilon}{n})$ since there are $p = O(\log_{1+\epsilon} n)$ rounds (Section~\ref{sec:main}), each of which is completed in $O(D)$ time (Section~\ref{sec:counting}). Note that step 9 of Algorithm~\ref{algo:maintain} can be done in a single round since every node already knows $m_{j}/n_{j}$ and can easily check, in one round, the number of neighbors in $G_{t'}$ that are in $V_{j}$.

When the nodes need to compute an approximation to the at-least-$k$-densest subgraph in Algorithm~\ref{algo:densest}, they can do so by choosing the densest subgraph among the last complete family of subgraphs found by Algorithm~\ref{algo:maintain}. Unfortunately, there is no guarantee that the densest such graph has at least $k$ nodes in it, so we fix this via padding. The subgraph is padded to contain at least $k$ nodes by having each node that is not part of the subgraph attempt to join the subgraph with an appropriate probability. It can be shown via Chernoff bounds that, with high probability, within $O(\log{n})$ such attempts there are enough nodes added to the subgraph to get its size to at least $k$. As a result, Algorithm~\ref{algo:densest} runs in $O(D\log{n})$ time. 
